#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    """
    @param: root: The root of the binary search tree.
    @param: node: insert this node into the binary search tree
    @return: The root of the new binary search tree.
    """
    def insertNode(self, root, node):
        # return self.rec_insert(root, node)
        return self.loop_insert(root, node)

    def loop_insert(self, root, node):
        if not root:
            return node

        cur = root
        while cur:
            parent = cur
            if node.val < cur.val:
                cur = cur.left
            elif node.val > cur.val:
                cur = cur.right
            else:
                assert False
            ## 每次都判断if cur.left, cur.right 很耗性能
            # if node.val < cur.val:
            #     if cur.left:
            #         cur = cur.left
            #     else:
            #         cur.left = node
            #         break
            # else:
            #     if cur.right:
            #         cur = cur.right
            #     else:
            #         cur.right = node
            #         break
        if node.val < parent.val:
            parent.left = node
        else:
            parent.right = node

        return root

    def rec_insert(self, root, node):
        if not root:
            return node

        if node.val < root.val:
            root.left = self.rec_insert(root.left, node)
        else:
            print("here")
            root.right = self.rec_insert(root.right, node)

        return root


def main():
    print("start main")
    root = TreeNode(5)

    s = Solution()
    root = s.insertNode(root, TreeNode(6))
    print(root.right.val)

if __name__ == "__main__":
    main()
